# https://leetcode.cn/problems/3sum/
# 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
# 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
# 你返回所有和为 0 且不重复的三元组
from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        # 枚举 target:nums[i] = - (nums[j]+nums[k])
        l = []
        n = len(nums)
        for i in range(n-2): # 保证 j和 k不相同，前面的任意元素都可以为 i
            target = nums[i]
            if i > 0 and target == nums[i-1]:
                continue # 如果和上一个元素相等，跳过重复元素
            j = i+1 # left
            k = n-1 # right
            while j < k:
                total = target + nums[j] + nums[k]
                if total < 0:
                    j += 1
                elif total > 0:
                    k -= 1
                else:
                    l.append([target,nums[j],nums[k]])
                    while j < k and nums[j] == nums[j+1]:
                        j += 1  # 跳过重复的元素
                    while j < k and nums[k] == nums[k-1]:
                        k -= 1  # 跳过重复的元素
                    j += 1 # 继续查找三元组
                    k -= 1
        return l
sl = Solution()
print(sl.threeSum([-1,0,1,2,-1,-4]))
